"""P7 7.图"""

"""
搜索二叉树：左子树比自己小，右子树比自己大
判断搜索二叉树：
方法1：中序遍历是升序的
方法2：左右子树都是搜索二叉树，左子树最大值小于根节点，右子树的最小值大于根节点

判断完全二叉树：宽度优先遍历
1、任一节点有右无左返回False
2、在不违反条件1的情况下，第一个无两个子节点的节点，它的后续节点都无子节点

判断满二叉树：
方法1：最大深度L，节点数N，满足：N = 2 ** L - 1
                           (1 << L 表示 2 ** L)
方法2：左右子树都是满二叉树且高度相等

判断平衡二叉树：
左右子树都是平衡二叉树，左右子树高度差小于等于1

解决树形DP（动态规划）：
向子节点索取相关信息，判断处理，返回相关信息。（注意叶节点Base情况的处理）

"""


class TreeNode:
    """二叉树节点"""

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def is_bst(head: TreeNode):
    """判断是否为搜索二叉树"""
    if head is None:
        return None

    left = is_bst(head.left)
    right = is_bst(head.right)
    min_value = max_value = head.value
    if left:
        min_value = min(min_value, left[1])
        max_value = max(max_value, left[2])
    if right:
        min_value = min(min_value, right[1])
        max_value = max(max_value, right[2])

    check = True
    if left:
        check = left[0] and left[2] < head.value
    if right:
        check = check and right[0] and head.value < right[1]

    return check, min_value, max_value


def is_cbt(head: TreeNode) -> bool:
    """判断是否为完全二叉树"""
    if head is None:
        return True
    no_children = False
    queue = [head]
    while queue:
        head = queue.pop(0)
        # 1、任一节点有右无左返回False
        # 2、在不违反条件1的情况下，第一个无两个子节点的节点，它的后续节点都无子节点
        if (no_children and (head.left or head.right)) \
                or (head.left is None and head.right):
            return False
        if head.left:
            queue.append(head.left)
        if head.right:
            queue.append(head.right)
        # 第一个无两个子节点的节点
        if head.left is None or head.right is None:
            no_children = True
    return True


def is_full_tree(head: TreeNode):
    """判断是否为满二叉树"""
    if head is None:
        return True, 0
    left = is_full_tree(head.left)
    right = is_full_tree(head.right)
    check = left[0] and right[0] and left[1] == right[1]
    height = max(left[1], right[1]) + 1
    return check, height


def is_balanced_tree(head: TreeNode) -> tuple:
    """判断是否为平衡二叉树"""
    if head is None:
        return True, 0
    left = is_balanced_tree(head.left)
    right = is_balanced_tree(head.right)
    is_balanced = left[0] and right[0] and abs(left[1] - right[1]) < 2
    height = max(left[1], right[1]) + 1
    return is_balanced, height


def lowest_ancestor(head: TreeNode, node1: TreeNode, node2: TreeNode):
    """找到树中节点node1、node2的最低公共祖先节点"""
    # node1是node2的子节点就返回node2
    if head is None or head == node1 or head == node2:
        return head
    left = lowest_ancestor(head.left, node1, node2)
    right = lowest_ancestor(head.right, node1, node2)
    if left and right:
        return head
    return left if left else right


class ParentNode:

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None


def get_successor_node(head: ParentNode):
    """寻找后继节点"""
    """
    1、Node有右子树，后继节点为右子树最左子节点
    2、Node无右子树，向上寻找，后继节点的左子树包含Node
    """
    if head is None:
        return None
    if head.right:
        head = head.right
        while head.left:
            head = head.left
        return head
    else:
        parent = head.parent
        # 根节点的parent为None
        while parent and parent.left != head:
            parent = parent.parent
        return parent


def serialization_tree(head: TreeNode) -> str:
    """二叉树的序列化(先序遍历)"""
    if head is None:
        return "#_"
    result = f"{head.value}_"
    result += serialization_tree(head.left)
    result += serialization_tree(head.right)
    return result


def deserialization_tree(string: str):
    """二叉树的反序列化(先序遍历)"""
    data = string.split("_")
    if data[0] == "#":
        return None
    head = TreeNode(int(data[0]))
    head.left = deserialization_tree(string[2:])
    head.right = deserialization_tree(string[4:])
    return head


def print_all_folds(N: int, layer: int = 1, result: str = "凹"):
    """打印纸条对折N次后的折痕凹凸情况"""
    # 本质上是中序遍历N层的满二叉树，每个节点的子节点左凹右凸
    if layer > N:
        return
    print_all_folds(N, layer + 1, "凹")
    print(result)
    print_all_folds(N, layer + 1, "凸")
